#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int getRandom(vector<int>& nums, int left, int right)
    {
        int r = rand();
        return nums[r%(right-left+1)+left];
    }

    void qsort(vector<int>& nums, int begin, int end)
    {
        if(begin >= end)
            return;
        int k = getRandom(nums, begin, end);
        int left = begin-1, right = end+1, cur = begin;
        while(cur < right)
        {
            if(nums[cur] < k)
            {
                swap(nums[cur++], nums[++left]);
            }
            else if(nums[cur] == k)
            {
                cur++;
            }
            else
            {
                swap(nums[cur], nums[--right]);
            }
        }
        qsort(nums, begin, left);
        qsort(nums, right, end);
    }

    vector<int> sortArray(vector<int>& nums)
    {
        srand(time(NULL));
        qsort(nums, 0, nums.size()-1);
        return nums;
    }
};